package org.datacoder.geocoding.datastructures.rectangles

import org.datacoder.geocoding.*
import org.datacoder.geocoding.datastructures.geoshapes.*
import org.datacoder.geocoding.datastructures.util.*
import org.datacoder.geocoding.jurisdiction.Jurisdiction

class LayeredIntervalTree implements RectanglesContainingPointFinder {

    public LayeredIntervalTreeNode root

    public LayeredIntervalTree(Collection<Jurisdiction> jurisdictions){
        List<GeoRectangle> geoRectangles = new ArrayList<GeoRectangle>()
        for(juris in jurisdictions){
            geoRectangles.add(juris.toGeoRectangle())
        }
        root = createNode(geoRectangles)
    }

    public LayeredIntervalTreeNode createNode(List<GeoRectangle> geoRectangles){
        if(geoRectangles.isEmpty()){
            return null
        }

        LayeredIntervalTreeNode litNode = new LayeredIntervalTreeNode()

        Collections.sort(geoRectangles, new GeoRectangleStartPointComparator(GeoShape.LON))
        int numGeoRectangles = geoRectangles.size()
        litNode.center = geoRectangles.get((Integer)(numGeoRectangles/2)).retrieveCenter(GeoShape.LON)

        List<GeoRectangle> leftGeoRectangles = new ArrayList<GeoRectangle>()
        List<GeoRectangle> centerGeoRectangles = new ArrayList<GeoRectangle>()
        List<GeoRectangle> rightGeoRectangles = new ArrayList<GeoRectangle>()

        int i
        for(i = 0; i < numGeoRectangles; i++){
            GeoRectangle gr = geoRectangles.get(i)
            if(gr.lon1 > litNode.center){
                break
            }
            if(gr.lon2 > litNode.center){
                centerGeoRectangles.add(gr)
            }else{
                leftGeoRectangles.add(gr)
            }
        }
        for(; i < numGeoRectangles; i++){
            rightGeoRectangles.add(geoRectangles.get(i))
        }
        litNode.left = createNode(leftGeoRectangles)
        litNode.lsiTree = new LayeredSubIntervalTree(centerGeoRectangles)
        litNode.right = createNode(rightGeoRectangles)
        return litNode
    }

    public Set<Jurisdiction> findRectanglesContainingPoint(GeoPoint gp){
        Set<Jurisdiction> jurisdictions = new HashSet<Jurisdiction>()
        LayeredIntervalTreeNode litNode = root
        while(litNode != null){
            jurisdictions.addAll(litNode.lsiTree.findRectanglesContainingPoint(gp))
            if(gp.lon == litNode.center){
                break
            }else if(gp.lon < litNode.center){
                litNode = litNode.left
            }else{
                litNode = litNode.right
            }
        }
        return jurisdictions
    }
}

